package main

import "fmt"

//我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。
//
// 实现一个叫「餐盘」的类 DinnerPlates：
//
//
// DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
// void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
// int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
// int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -
//1。
//
//
//
//
// 示例：
//
// 输入：
//["DinnerPlates","push","push","push","push","push","popAtStack","push","push",
//"popAtStack","popAtStack","pop","pop","pop","pop","pop"]
//[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
//输出：
//[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]
//
//解释：
//DinnerPlates D = DinnerPlates(2);  // 初始化，栈最大容量 capacity = 2
//D.push(1);
//D.push(2);
//D.push(3);
//D.push(4);
//D.push(5);         // 栈的现状为：    2  4
//                                    1  3  5
//                                    ﹈ ﹈ ﹈
//D.popAtStack(0);   // 返回 2。栈的现状为：      4
//                                          1  3  5
//                                          ﹈ ﹈ ﹈
//D.push(20);        // 栈的现状为：  20  4
//                                   1  3  5
//                                   ﹈ ﹈ ﹈
//D.push(21);        // 栈的现状为：  20  4 21
//                                   1  3  5
//                                   ﹈ ﹈ ﹈
//D.popAtStack(0);   // 返回 20。栈的现状为：       4 21
//                                            1  3  5
//                                            ﹈ ﹈ ﹈
//D.popAtStack(2);   // 返回 21。栈的现状为：       4
//                                            1  3  5
//                                            ﹈ ﹈ ﹈
//D.pop()            // 返回 5。栈的现状为：        4
//                                            1  3
//                                            ﹈ ﹈
//D.pop()            // 返回 4。栈的现状为：    1  3
//                                           ﹈ ﹈
//D.pop()            // 返回 3。栈的现状为：    1
//                                           ﹈
//D.pop()            // 返回 1。现在没有栈。
//D.pop()            // 返回 -1。仍然没有栈。
//
//
//
//
// 提示：
//
//
// 1 <= capacity <= 20000
// 1 <= val <= 20000
// 0 <= index <= 100000
// 最多会对 push，pop，和 popAtStack 进行 200000 次调用。
//
// Related Topics 设计
// 👍 24 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
type DinnerPlates struct {
	Stacks [][]int
	LeftIndex int //  最左边不为空的栈
	RightIndex int // 最右边第一个非空栈
	Cap int // 容量
}

func Constructor(capacity int) DinnerPlates {
	var stacks [][]int
	return DinnerPlates{
		Stacks:      stacks,
		LeftIndex:  -1, // 初始化
		RightIndex: -1, // 初始化
		Cap: capacity, // 初始化容量
	}
}


func (this *DinnerPlates) Push(val int)  {
	if this.Cap == 0 {
		return
	}

	if this.LeftIndex == -1 || len(this.Stacks[this.LeftIndex]) == this.Cap {
		var stacks [][]int
		var stack []int
		stack = append(stack, val)
		stacks = append(stacks, stack)
		this.Stacks = append(this.Stacks, stacks...)
		this.LeftIndex++
	} else {
		leftIndexStack := this.Stacks[this.LeftIndex]
		// 未满, 直接添加
		leftIndexStack = append(leftIndexStack, val)
		this.Stacks[this.LeftIndex] = leftIndexStack
		if len(leftIndexStack) == this.Cap {
			// 添加后已满,. 移动 leftIndex
			for i, v := range this.Stacks[this.LeftIndex+1:] {
				if len(v) < this.Cap {
					this.LeftIndex = this.LeftIndex+1+i
					break
				}
			}
		}
	}
	for i := len(this.Stacks) - 1; i >= 0; i-- {
		if len(this.Stacks[i]) > 0 {
			this.RightIndex = i
			break
		}
	}
}


// 返回从右往左的第一个非空栈的值, 并吧它删除
func (this *DinnerPlates) Pop() int {
	if this.RightIndex == -1 {
		return -1
	}

	rightStack := this.Stacks[this.RightIndex]

	if len(rightStack) == 0 {
		return -1
	}
	rightVal := rightStack[len(rightStack) - 1]
	rightStack = rightStack[:len(rightStack) - 1]
	this.Stacks[this.RightIndex] = rightStack
	//if len(rightStack) == 0 {
		//this.RightIndex--
		//if this.LeftIndex > this.RightIndex {
		//	this.LeftIndex = this.RightIndex
		//}
	//}

	for i := len(this.Stacks) - 1; i >= 0; i-- {
		if len(this.Stacks[i]) > 0 {
			this.RightIndex = i
			break
		}
	}
	
	return rightVal
}
// 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1
func (this *DinnerPlates) PopAtStack(index int) int {
	if index < 0 || index >= len(this.Stacks) {
		return -1
	}

	stack := this.Stacks[index]
	if len(stack) == 0 {
		return -1
	}
	
	val :=  stack[len(stack) - 1]
	stack = stack[0:len(stack) -1]
	this.Stacks[index] = stack

	// 重新计算索引
	for i, v := range this.Stacks {
		if len(v) <= this.Cap {
			this.LeftIndex = i
			break
		}
	}

	for i := len(this.Stacks) - 1; i >= 0; i-- {
		if len(this.Stacks[i]) > 0 {
			this.RightIndex = i
			break
		}
	}
	return val
}

func main() {
	//// ["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
	//// [[2], [1], [2], [3], [4], [5], [0],[20],[21],[0],[2],[],[],[],[],[]]
	//// [null,null,null,null,null,null,2,  null,null,20, 21, 5, 4, 3, 1, -1]
	//dinnerPlates := Constructor(2)
	//dinnerPlates.Push(1)
	//dinnerPlates.Push(2)
	//dinnerPlates.Push(3)
	//dinnerPlates.Push(4)
	//dinnerPlates.Push(5)
	//fmt.Printf("%#v \n", dinnerPlates)
	//dinnerPlates.PopAtStack(0)
	//fmt.Printf("%#v \n", dinnerPlates)
	//dinnerPlates.Push(20)
	//dinnerPlates.Push(21)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val := dinnerPlates.PopAtStack(0)
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.PopAtStack(2)
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val  = dinnerPlates.Pop()
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.Pop()
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.Pop()
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.Pop()
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.Pop()
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)


	//	["DinnerPlates","push","push","push","popAtStack","pop","pop"]
	//	[[1],			[1],	[2],	[3],  [1],		   [],	 []  ]
	//dinnerPlates := Constructor(1)
	//dinnerPlates.Push(1)
	//dinnerPlates.Push(2)
	//dinnerPlates.Push(3)
	//val := dinnerPlates.PopAtStack(1)
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.Pop()
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.Pop()
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)

	//	["DinnerPlates","push","push","popAtStack","popAtStack","push","popAtStack"]
	//  [[1],			[1],	[2],	[0],		[1],		[3],	[0]]
	//	[null,			null,	null,	1,			2,			null,	3]

	//dinnerPlates := Constructor(1)
	//dinnerPlates.Push(1)
	//fmt.Printf("%#v \n", dinnerPlates)
	//dinnerPlates.Push(2)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val := dinnerPlates.PopAtStack(0)
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.PopAtStack(1)
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)
	//dinnerPlates.Push(3)
	//fmt.Printf("%#v \n", dinnerPlates)
	//val = dinnerPlates.PopAtStack(0)
	//fmt.Println(val)
	//fmt.Printf("%#v \n", dinnerPlates)

	//["DinnerPlates","push","push","popAtStack","pop","push","push","pop","pop"]
	//[[1],			  [1],	  [2],   [1],        [],    [1],   [2],   [],   []]
	//[null,		  null,	   null,  2,		 1,	    null,	null, 2,    1]
	dinnerPlates := Constructor(1)
	dinnerPlates.Push(1)
	fmt.Printf("%#v \n", dinnerPlates)
	dinnerPlates.Push(2)
	fmt.Printf("%#v \n", dinnerPlates)
	val := dinnerPlates.PopAtStack(1)
	fmt.Println(val)
	fmt.Printf("%#v \n", dinnerPlates)
	val = dinnerPlates.Pop()
	fmt.Println(val)
	fmt.Printf("%#v \n", dinnerPlates)
	dinnerPlates.Push(1)
	fmt.Printf("%#v \n", dinnerPlates)
	dinnerPlates.Push(2)
	fmt.Printf("%#v \n", dinnerPlates)
	val = dinnerPlates.Pop()
	fmt.Println(val)
	fmt.Printf("%#v \n", dinnerPlates)
	val = dinnerPlates.Pop()
	fmt.Println(val)
	fmt.Printf("%#v \n", dinnerPlates)
}
